package leetcode012;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.cn/problems/integer-to-roman/
 * 12. 整数转罗马数字
 * 七个不同的符号代表罗马数字，其值如下：
 *
 * 符号	值
 * I	1
 * V	5
 * X	10
 * L	50
 * C	100
 * D	500
 * M	1000
 * 罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：
 *
 * 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
 * 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
 * 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。
 * 给定一个整数，将其转换为罗马数字。
 *
 *
 */
public class Study012 {


    public String intToRoman(int num) {
        Map<Integer, String> map = initData();
        List<Integer> numList = new ArrayList<>();
        while (num > 0) {
            numList.add((int)(num % 10  * Math.pow(10, numList.size())));
            num = num / 10;
        }
        List<String> resultList = new ArrayList<>();
        for (int i = 0; i < numList.size(); i++) {
            StringBuilder symbol = new StringBuilder();
            int cur = numList.get(i);
            int head = (int) (cur / Math.pow(10, i));
            if (head == 4 || head == 9) {
                symbol.append(map.get((int) Math.pow(10, i)));
                symbol.append(map.get(cur + (int) Math.pow(10, i)));
            } else if (head < 4) {
                while (cur > 0) {
                    cur = cur - (int) (Math.pow(10, i));
                    symbol.append(map.get((int) (1 * Math.pow(10, i))));
                }
            } else if (head < 9) {
                cur = cur - (int) (5 * Math.pow(10, i));
                symbol.append(map.get((int) (5 * Math.pow(10, i))));
                while (cur > 0) {
                    cur = cur - (int) (Math.pow(10, i));
                    symbol.append(map.get((int) (1 * Math.pow(10, i))));
                }
            }
            resultList.add(symbol.toString());
        }
        StringBuilder result = new StringBuilder();
        for (int i = resultList.size() - 1; i >= 0; i--) {
            result.append(resultList.get(i));
        }
        return result.toString();
    }

    private Map<Integer, String> initData() {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "I");
        map.put(5, "V");
        map.put(10, "X");
        map.put(50, "L");
        map.put(100, "C");
        map.put(500, "D");
        map.put(1000, "M");
        return map;
    }

    public String intToRoman2(int num) {
        int[] romaNums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romaSymbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder symbol = new StringBuilder();
        for (int i = 0; i < romaNums.length; i++) {
            while (num >= romaNums[i]) {
                num -= romaNums[i];
                symbol.append(romaSymbols[i]);
            }
        }
        return symbol.toString();
    }


    public static void main(String[] args) {
        Study012 s = new Study012();
        System.out.println(s.intToRoman2(3749) + " " + s.intToRoman2(3749).equals("MMMDCCXLIX"));
    }
}
